package lc.q101_150;

import lc.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

public class Q107 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<List<TreeNode>> nodes = new ArrayList<>();
        nodes.add(Collections.singletonList(root));
        while (nodes.get(nodes.size() - 1).size() != 0) {
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode treeNode : nodes.get(nodes.size() - 1)) {
                if (treeNode.left != null) {
                    next.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    next.add(treeNode.right);
                }
            }
            nodes.add(next);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = nodes.size() - 1; i >= 0; i--) {
            if (nodes.get(i).size() == 0) {
                continue;
            }
            result.add(nodes.get(i).stream().map(n -> n.val).collect(Collectors.toList()));
        }
        return result;
    }
}
